1. Technical Field of the Invention
This invention relates generally to the field of communication networks. More specifically the present invention relates to rank deficient decoding of linear network coding.
2. Background
Communications networks (CNs) are ubiquitous in our everyday life as well as our national infrastructure. Network coding [1] has the potential to fundamentally transform current and future CNs due to the promise of significant throughput gains. Furthermore, network coding has other advantages such as robustness and can be implemented in a distributed manner with random linear network coding[2]. Hence, network coding is already used or considered for a wide variety of wired and wireless networks.
One significant drawback of network coding is its all-or-nothing property in more than one sense. First, a full rank of received packets at the receiver nodes is needed before decoding can start, leading to long delays and low throughputs, especially when the number of packets of a session is large. This is particularly undesirable for military and civil applications with stringent delay requirements. Second, all the bits in any packet are “created equal” in the sense that they are recovered simultaneously.
Network coding is a network paradigm where packets can be operated on or mixed. It has been shown that network coding improves the network throughput and robustness to network failures. Although network coding is first applied to packets, this idea has later been applied to waveforms on the physical layer.
It has been shown that in most practical scenarios, linear network coding is close to optimal. Furthermore, in all existing linear network coding schemes, a full rank decoder is used. A full rank decoder fails unless the rank of the received packets is the same as that of the transmitted packets.
3. The Prior Art
U.S. Pat. No. 8,473,998 to Lucani et al. discloses a method, apparatus and computer program product for utilizing network coding for multi-resolution multicast. A network source partitions source content into a base layer and one or more refinement layers. The network source receives a respective one or more push-back messages from one or more network destination receivers, the push-back messages identifying the one or more refinement layers suited for each one of the one or more network destination receivers. The network source computes a network code involving the base layer and the one or more refinement layers for at least one of the one or more network destination receivers, and transmits the network code to the one or more network destination receivers in accordance with the push-back messages.
U.S. Pat. No. 8,046,426 to Medard et al. discloses a method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.
U.S. Pat. No. 8,375,102 to Medard et al. discloses a method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.
U.S. Pat. No. 8,102,837 to Deb et al. discloses a method, apparatus and computer program product for providing rapid information dissemination using network coding is presented. A coded message including a payload and a code vector, is transmitted from a first node of the network to a second node of the network. The information thus stored can also be retrieved by collecting code vectors from at least one node and viewing the collected code vectors as a matrix. A determination is made regarding whether a dimension of the matrix is equal to a predefined number. When the dimension of the matrix equals the predefined number, the information is retrieved using the collection of code vectors in the matrix.
All network coding schemes in the prior art assume a full rank decoder. Hence, more received packets are needed before decoding starts.